package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         215,
		Discription: "Kth",
		Level:       2,
		Labels: map[string]int{
			"快排": 1,
			"堆排": 1,
		},
	})
}

func FindKthLargest(nums []int, k int) int {
	n := len(nums)
	return fastSelect(nums, 0, n-1, n-k)
}

func fastSelect(nums []int, start int, end int, k int) int {
	if start >= end {
		return nums[start]
	}

	//和快排类似，le...re中的值在数组中的位置是已确定的
	le, re := threePartition(nums, start, end)
	if le <= k && k <= re {
		return nums[k]
	}

	if k > re {
		return fastSelect(nums, re+1, end, k)
	} else {
		return fastSelect(nums, start, le-1, k)
	}
}

//分成三部分：小于pivotVal,=，>
//[le:re+1]是等于的部分
func threePartition(nums []int, start int, end int) (int, int) {
	i := start
	le := start
	re := end
	pivotVal := nums[i]
	//将pivotVal移到最后，一开始默认所有都比pivotVal小
	nums[start], nums[end] = nums[end], nums[start]

	for i <= re {
		if nums[i] == pivotVal {
			i++
			continue
		}

		if nums[i] > pivotVal {
			nums[i], nums[re] = nums[re], nums[i]
			//比pivotVal大，从后面换过来的值还没被判断过，所以不能i++
			re--
		} else {
			nums[i], nums[le] = nums[le], nums[i]
			i++
			le++
		}
	}

	return le, re
}

//堆排：建堆O（n）,调整O（klog n）
/* func findKthLargest(nums []int, k int) int {
	buildHeap(nums)
	bottom := len(nums) - 1
	for i := 1; i < k; i++ {
		nums[0], nums[bottom-i+1] = nums[bottom-i+1], nums[0]
		adjustHeap(nums, 0, bottom-i)
	}

	return nums[0]
}

func buildHeap(nums []int) {
	for i := len(nums)/2 - 1; i >= 0; i-- {
		adjustHeap(nums, i, len(nums)-1)
	}
}

func adjustHeap(nums []int, start int, end int) {
	i := start
	topValue := nums[start]
	for 2*i+1 <= end {
		var biggerChildIndex int
		leftChildIndex := 2*i + 1
		rightChildIndex := 2*i + 2
		if rightChildIndex > end {
			biggerChildIndex = leftChildIndex
		} else {
			if nums[leftChildIndex] >= nums[rightChildIndex] {
				biggerChildIndex = leftChildIndex
			} else {
				biggerChildIndex = rightChildIndex
			}
		}

//用topValue比！找的是topValue安家的位置
        if topValue>=nums[biggerChildIndex]{
            break
        }

		nums[i] = nums[biggerChildIndex]
		i = biggerChildIndex
	}

	nums[i] = topValue
} */
